package com.andnnl.num;

/**
 * 魔术索引
 * Created by chenss on 2021/4/16.
 */
public class MagicIndexTest {
    public static void main(String[] args) {
//        int[] arr={1,2,4,6,6,6,6,8,10,11,12,13,14,14,14,15,15,15,15,17,18,19,20};
        int[] arr={1,2,4,6,6,6,6,8,10,11,12,13,20,20,20,20,20,20,20,20,22,22,22};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(i+"\t"+arr[i]);
        }
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;			//定义middle
        int count=0;
        boolean isFind=false;
        while(low <=high){
            count++;
            middle = (low + high) / 2;
            if(middle > arr[middle]){
                //比关键字大则关键字在左区域
                high = middle - 1;
            }else if(middle < arr[middle]){
                //比关键字小则关键字在右区域
                low = middle + 1;
            }else{
                System.out.println("find:"+middle);
                isFind=true;
                break;
            }
        }
        System.out.println(isFind);
        System.out.println("count:"+count);

    }
}
